#include <bits/stdc++.h>

using namespace std;

/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
int maxSubArray(vector<int> &nums)
{
    // write your code here
    if(nums.empty())
        return 0;
    int sum = 0, maxSum = INT_MIN;
    for(int i = 0; i < nums.size(); i++){
        sum += nums[i];
        if(sum > maxSum)
            maxSum = sum;
        if(sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main()
{
    vector<int> nums = {-2, 2, -3, 4, -1, 2, 1, -5, 3};
    nums = {-2};
//    nums = {};
//    nums = {5};
//    nums = {-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-1000};
    printf("%d", maxSubArray(nums));
    return 0;
}

/**
最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
注意事项

子数组最少包含一个数
您在真实的面试中是否遇到过这个题？
样例

给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
*/

/**
算法思想：贪心法，复杂度O（n）

将子串和为负数的子串丢掉，只留和为正的子串。使用sum来计算当前连续子数组的和，如果sum小于0，
那么无论后面再加上什么数字都只会让子数组变小，所以抛弃当前子数组，重新开始计算子数组的值。

参考：https://blog.csdn.net/sinat_30440627/article/details/54924737
*/
